/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        876.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/9 9:48
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//给定一个头结点为 head 的非空单链表，返回链表的中间结点。
//
//如果有两个中间结点，则返回第二个中间结点
#include "../header.h"

class Solution {
public:
//    ListNode* middleNode(ListNode* head) {
//        ListNode *fast,*slow;
//        fast = slow = head;
//        while (fast != nullptr && fast->next != nullptr){
//            fast=fast->next->next;
//            slow = slow->next;
//        }
//        return slow;
//    }
    ListNode *middleNode(ListNode *head) {
        vector<ListNode *> vec{head};
        while (vec.back()->next != nullptr)
            vec.emplace_back(vec.back()->next);
        return vec[vec.size()/2];
    }
};
